#include<iostream>
#include<cmath>
#include<iomanip>
#include<vector>
#define  PI 3.1415926 //假定PI值
using namespace std;

//用来精确7位小数
double p = 1e-7;


//第一题-------------------------------------------------------------------------------------------------------
//二分法近似的方程表达式
double func(double x){
	return x * x * x - 3 * x - 1;
}
//二分法近似
void Dichotomy() {
	double max = 3;
	double min = 1;
	double mid = (max + min) / 2;
	if (func(mid) != 0) {
		while (abs(func(mid)) > p) {
			if (func(mid) * func(min) > 0) {
				min = mid;
			}
			else {
				max = mid;
			}
			mid = (max + min) / 2;
		}
	}
	cout << "二分法近似结果：" << setprecision(8) << mid << endl;
}

//牛顿法近似
void Newton() {
		double appro, actual, iter, destination = 4;
		do {
			iter = destination;
			appro = 3 * iter * iter - 3;//近似方程
			actual = iter * iter * iter - 3 * iter - 1;//实际方程
			destination = iter - actual / appro;//用最终结果去减两个方程的商，逐渐迭代
		} while (abs(iter - destination) > p);
		cout << "牛顿法近似结果：" << setprecision(8) << destination << endl;
}

void text_1(){
    cout << "第一题" << endl;
    cout<< "2cos20 " << " = " << setprecision(8) << 2 * cos(PI / 9) << endl;//注意cos的传入值是弧度制
	Dichotomy();
	Newton();
	cout << "----------------------------------------------" << endl << endl;
}

//第二题---------------------------------------------------------------------------------------------------
void text_2(){
    cout << "第二题" << endl;
    int total = 100; // 总金额
    int one, two, five, ten; // 分别代表1元、2元、5元和10元的数量
	int sum = 0; //记录分法

    // 由于每种零钞至少有一张，所以从1开始遍历
    for (ten = 1; ten <= total / 10; ++ten) {
        for (five = 1; five <= (total - 10 * ten) / 5; ++five) {
            for (two = 1; two <= (total - 10 * ten - 5 * five) / 2; ++two) {
                one = total - 10 * ten - 5 * five - 2 * two;
                // 确保每种零钞至少有一张
                if (one >= 1) {
					sum += 1;
                    cout << "10元: " << ten << "张, 5元: " << five << "张, 2元: " << two << "张, 1元: " << one << "张" << endl;
                }
            }
        }
    }
    cout << "共有" << sum << "种分法" << endl;
    cout << "----------------------------------------------" << endl;
}

//第三题--------------------------------------------------------------------------------------------------------
void text_3(){
    cout << "第三题" << endl;
    vector<int>temp = {3,4,0,2,2,0,2,3,5,2,3,2,1,3,3,2,5,1};
    int n = temp.size();
    vector<int>dp(n + 1, 0x3f3f3f);
    dp[0] = 1;
    for(int i = 1; i <= n; i ++){
        for(int j = i - 1; j >= 0; j --){
            if(dp[j] == 0)continue;
            if(j + temp[j] >= i)dp[i] = min(dp[i], dp[j]+1);
        }
    }
    if(dp[n] == 0x3f3f3f)cout << "-1" << endl;
    else cout << dp[n]-1 << endl;
    cout << "----------------------------------------------" << endl;
}


int main() {
	text_1();
	text_2();
	text_3();
	return 0;
}
